package org.simtube.index;

import java.util.Arrays;
import java.util.Iterator;
import java.util.Random;

import org.simtube.util.DocVector;
import org.simtube.util.EntryComparator;
import org.simtube.util.OrderedEntryQueue;

public class CSRTree {
	private CNode root;
	private int m;
	private int M;
	private OrderedEntryQueue queue;
	
	/**
	 * Create a CSRTree, where m is the minimal entries in a non-root node,
	 * M is the maximum number of entries in a node
	 * 
	 * @param m
	 * @param M
	 */
	public CSRTree(int m, int M) {
		this.m = m;
		this.M = M;
		root = null;
	}
	
	/**
	 * Search for k regions nearest to the query region q
	 *  
	 * @param q The query region
	 * @param k Number of regions that will be returned
	 * @return k nearest neighbors if the tree contains more than or equal to
	 * k data records, otherwise return all records in the tree
	 */
	public int[] kNNSearch(Region q, int k) {
		queue = new OrderedEntryQueue(k, q);
		searchNode(root, q);
		
		CEntry[] elist = queue.toArray();
		int[] ilist = new int[elist.length];
		
		for(int i = 0; i < ilist.length; i++)
			ilist[i] = elist[i].getIndex();
		
		// queue.printQueue();
		
		return ilist;
	}
	
	/**
	 * Conduct nearest neighbor search on a node and its descendants
	 * 
	 * @param n The current root node
	 * @param q The Query region
	 */
	private void searchNode(CNode n, Region q) {
		if(n == null) return;
		
		CEntry[] elist = new CEntry[n.size()];
		
		Iterator<CEntry> it = n.getElist().iterator();
		
		for(int i = 0; i < elist.length; i++) {	
			elist[i] = it.next();
		}
		
		Arrays.sort(elist, new EntryComparator(q));
		
		for(int i = 0; i < elist.length; i++) {
			if(queue.isFull() && 
					Region.distance(elist[i].getRegion(), q) >= queue.maxDistance())
				return;
			if(n.getType() == CNodeType.Leaf || n.getType() == CNodeType.RootAndLeaf)
				queue.insert(elist[i]);
			else
				searchNode(elist[i].getCNode(), q);
		}
	}
	
	/**
	 * Insert a record into the tree, the region and its record (index) should
	 * be specified.
	 * 
	 * @param r The region
	 * @param index The index in document matrix
	 */
 	public void insert(Region r, int index) {
		CEntry en = new CEntry(r, index);
		
		CNode n = chooseLeaf(root, en);
		CNode nn = null;
		
		n.getElist().add(en);
		en.setCurrentNode(n);
		
		if(n.size() > M)
			nn = n.split(m);
		
		adjustTree(n, nn);
	}
	
	/**
	 * Choose a proper leaf to do the insertion, here we adopted a greedy 
	 * strategy that we always choose the region that is nearest to the entry
	 * to be inserted.
	 * 
	 * @param n The current root node
	 * @param en The entry that will be inserted
	 * @return A leaf node that is proper to do the insertion
	 */
	private CNode chooseLeaf(CNode n, CEntry en) {
		
		if(root == null) {
			root = new CNode(CNodeType.RootAndLeaf, null);
			return root;
		}
		
		if(n.getType() == CNodeType.Leaf || n.getType() == CNodeType.RootAndLeaf)
			return n;
		
		Iterator<CEntry> it = n.getElist().iterator();
		double min = Double.MAX_VALUE;
		CEntry ce = null;
		double dist = 0;
		CEntry cemin = null;
		
		while(it.hasNext()) {
			ce = it.next();
			dist = Region.distance(ce.getRegion(), en.getRegion());
			if(dist < min) {
				min = dist;
				cemin = ce;
			}
		}
		
		return chooseLeaf(cemin.getCNode(), en);
	}
	
	/**
	 * Adjust tree after insertion. The region in relevant nodes may be changed.
	 * The adjustment starts from updating the covering region of node n, which
	 * is in its parent node's entry list. A new root node will be created if
	 * it is also split.
	 * 
	 * @param n The start node to adjust
	 * @param nn The split node if there is any
	 */
	private void adjustTree(CNode n, CNode nn) {
		
		CEntry en = null;
		
		if(n == root) {
			if(nn == null) return;
			
			CNode nroot = new CNode(CNodeType.Root, null);
			
			en = nn.createEntry();
			nn.setEntry(en);
			
			if(nn.getType() == CNodeType.Root)
				nn.setType(CNodeType.NonLeaf);
			else // RootAndLeaf
				nn.setType(CNodeType.Leaf);
			
			nroot.getElist().add(en);
			en.setCurrentNode(nroot);
			
			en = root.createEntry();
			root.setEntry(en);
			if(root.getType() == CNodeType.Root)
				root.setType(CNodeType.NonLeaf);
			else // RootAndLeaf
				root.setType(CNodeType.Leaf);
			
			nroot.getElist().add(en);
			en.setCurrentNode(nroot);
			
			root = nroot;
		} else {
			
			n.getEntry().setRegion(Region.minCoverRegion(n));
			CNode np = n.getEntry().getCurrentNode();
			
			if(nn == null) {
				adjustTree(np, null);
				return;
			}
			
			// System.out.println("Size of nn: " + nn.size());
			en = nn.createEntry();
			nn.setEntry(en);
			
			np.getElist().add(en);
			en.setCurrentNode(np);
			
			if(np.size() > M) {
				CNode nnp = np.split(m);
				adjustTree(np, nnp);
			} else {
				adjustTree(np, null);
			}
		}
	}
	
	/**
	 * Print tree to standard output
	 */
	public void printTree() {
		print(root, 0);
	}
	
	/**
	 * Print a single node and its descendants
	 * 
	 * @param r The current root node
	 * @param layer Which layer is the node on, used for formatting the output
	 */
	private void print(CNode r, int layer) {
		for(int i = 0; i < layer; i++)
			System.out.print("\t");
		System.out.println(r.getType() + " " + Region.minCoverRegion(r));
		
		Iterator<CEntry> it = r.getElist().iterator();
		
		while(it.hasNext()) {
			if(r.getType() != CNodeType.Leaf && r.getType() != CNodeType.RootAndLeaf)
				print(it.next().getCNode(), layer + 1);
			else
				print(it.next().getIndex() + "", layer + 1);
		}
	}
	
	private void print(String txt, int layer) {
		for(int i = 0; i < layer; i++)
			System.out.print("\t");
		System.out.println(txt);
	}
	
	public static void main(String[] args) {
		CSRTree tree = new CSRTree(10, 20);
		
		Random r = new Random();
		int n = 256;
		
		long start = System.nanoTime();
		for(int i = 0; i < 14035; i++) {
			double[] va = new double[n];
			for(int j = 0; j < n; j++)
				va[j] = r.nextDouble();
			
			Region reg = new Region(new DocVector(va).normalize(), 0);
			
			System.out.println((i + 1));
			
			tree.insert(reg, i);
		}
		long end = System.nanoTime();
		
		System.out.println("Time cost to build R-Tree: "
				+ (end - start) / 1000000 + "ms");
		
		/*
		start = System.nanoTime();
		for(int i = 0; i < 100; i++) {
			double[] vq = new double[n];
			for(int j = 0; j < n; j++) {
				vq[j] = r.nextDouble();
			}
			
			Region reg = new Region(new DocVector(vq).normalize(), 0);
			tree.kNNSearch(reg, 200);
			
			System.out.println((i + 1));
		}
		end = System.nanoTime();
		
		System.out.println("Time cost to do k-NN search: "
				+ (end - start) / 1000000 + "ms");
		*/
		// tree.printTree();
	}
}
